// https://leetcode.cn/problems/0H97ZC/

import "sort"
func relativeSortArray(arr1 []int, arr2 []int) []int {
	rec := make(map[int]int)
	for _, v := range(arr1) {
		rec[v]++
	}
	ans := []int{}
	for _, v := range(arr2) {
		for i, _ := rec[v]; i > 0; i-- {
			ans = append(ans, v)
		}
		delete(rec, v)
	}
	t := []int{}
	for k := range(rec) {
		for i, _ := rec[k]; i > 0; i-- {
			t = append(t, k)
		}
	}
	sort.Ints(t)
	return append(ans, t...)
}